// 518. 零钱兑换 II
// 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
// 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
// 假设每一种面额的硬币有无限个。
// 题目数据保证结果符合 32 位带符号整数。

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  const len = coins.length
  const dp = new Array(len + 1).fill(0).map(() => new Array(amount + 1).fill(0))

  for (let i = 0; i <= len; i++) {
    dp[i][0] = 1
  }

  for (let i = 1; i <= len; i++) {
    for (let j = 1; j <= amount; j++) {
      dp[i][j] = dp[i - 1][j]
      if (j - coins[i - 1] >= 0) {
        dp[i][j] += dp[i][j - coins[i - 1]]
      }
    }
  }

  return dp[len][amount]
}

console.log(
  change(
    5,
    [1, 2, 5]
  )
)











